class Solution {
public:
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
    int orangesRotting(vector<vector<int>>& grid) {
        //使用bfs解决，首先将被感染过的橘子放入到一个队列中，然后计算出所有完好橘子的个数
        //当进行感染的时候将这个受感染的橘子从队列中拿出来，然后将四周完好的橘子感染为腐烂橘子
        //然后将这些橘子放入到队列中，直到最后队列为空，如果此时还有橘子说明有橘子无法被感染到
        //同时每拿出一次队列中的橘子就是1分钟
        vector<pair<int,int>> arr;//记录腐烂橘子的数组
        int count = 0;
        int ret = -1;
        int m = grid.size();
        int n = grid[0].size();
        for(int i = 0;i<m;i++)
        {
            for(int j = 0;j<n;j++)
            {
                if(grid[i][j] == 2)
                {
                    arr.push_back(make_pair(i,j));
                }
                else if(grid[i][j] == 1)
                {
                    count++;
                }
            }
        }//记录下被感染的橘子，以及完好橘子的个数
        while(!arr.empty())
        {
            //拿取arr中的橘子进行感染
            ret++;//ret初始化为-1,因为一开始就存在腐烂的橘子会往外进行扩散
            vector<pair<int,int>> temp;//记录下新的被感染的橘子
            for(auto& e:arr)
            {
                for(int i = 0;i<4;i++)
                {
                    int newx = e.first+dx[i];
                    int newy = e.second+dy[i];
                    if(newx>=0&&newx<m&&newy>=0&&newy<n&&grid[newx][newy] == 1)
                    {
                        count--;//感染了一个橘子
                        grid[newx][newy] = 2;
                        temp.push_back(make_pair(newx,newy));
                    }
                }
            }
            arr = temp;//将新的值复制给arr
        }
        return count?-1:max(ret,0);//如果最后count不为0说明存在橘子无法被腐烂，返回-1，否则就返回
        //ret的值，这里使用一个max因为有一种情况是全是腐烂的橘子
    }
};